package dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 300. 最长递增子序列
 */
public class P300 {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        List<Integer> maxLenList = new ArrayList<>();
        maxLenList.add(0);
        backTrack(len, 0, nums, new ArrayList<>(), maxLenList);
        return maxLenList.get(0);
    }

    private void backTrack(int len, int begin, int[] nums, List<Integer> saved, List<Integer> maxLenList) {
        if (begin == len) {
            if (saved.size() >= maxLenList.get(0)) {
                maxLenList.set(0, saved.size());
            }
        } else {
            for (int i = begin; i < len; i++) {
                if (saved.size() == 0 || nums[i] > saved.get(saved.size() - 1)) {
                    // 选
                    saved.add(nums[i]);
                    backTrack(len, i + 1, nums, saved, maxLenList);
                    saved.remove(saved.size() - 1);
                    //不选
                    backTrack(len, i + 1, nums, saved, maxLenList);
                } else {
                    backTrack(len, i + 1, nums, saved, maxLenList);
                }
            }
        }

    }


    private int dp(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int max = 1;
        int[] dp = new int[len];
        dp[0] = 1;
        for (int i = 1; i < len; i++) {
            int idx = i - 1;
            int maxTimes = 0;
            for (; idx >= 0; idx--) {
                if (nums[idx] < nums[i] && maxTimes < dp[idx]) {
                    maxTimes = dp[idx];
                }
            }
            dp[i] = maxTimes + 1;
            if (dp[i] > max) {
                max = dp[i];
            }

        }
        return max;
    }

    public static void main(String[] args) {
        int i = new P300().dp(new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6});
        System.out.println(i);
    }
}
